/**
 * 有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
 *
 * 问最多能装入背包的总价值是多大?
 */
public class BackPackII {
    /**
     * 状态：
     *
     *  F(i, j): 前i个物品放入大小为j的背包中所获得的最大价值
     * 状态递推：对于第i个商品，有一种例外，装不下，两种选择，放或者不放
     *
     *  如果装不下：此时的价值与前i-1个的价值是一样的
     *
     *  F(i,j) = F(i-1,j)
     *
     *  如果可以装入：需要在两种选择中找最大的
     *
     *  F(i, j) = max{F(i-1,j), F(i-1, j - A[i]) + V[i]}
     *
     *  F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
     *
     *  F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出j - A[i]的大小放第i个商品
     * 初始化：第0行和第0列都为0，表示没有装物品时的价值都为0
     *
     *  F(0,j) = F(i,0) = 0
     *
     * 返回值：F(n,m)
     */
//    public int backPackII(int m, int[] a, int[] v) {
//        // write your code here
//        int len=a.length;
//        int[][] maxValue=new int[len+1][m+1];
//        for(int i=1;i<=len;i++) {
//            for(int j=1;j<=m;j++) {
//                if(a[i-1]<=j) {
//                    maxValue[i][j]=Math.max(maxValue[i-1][j],maxValue[i-1][j-a[i-1]]+v[i-1]);
//                } else {
//                    maxValue[i][j]=maxValue[i-1][j];
//                }
//            }
//        }
//        return maxValue[len][m];
//    }

    /**
     * 空间优化
     * @param m
     * @param a
     * @param v
     * @return
     */
    public int backPackII(int m, int[] a, int[] v) {
        // write your code here
        int n=a.length;
        int[] maxValue=new int[m+1];
        for(int i=1;i<=n;i++) {
            for(int j=m;j>0;j--) {
                if(a[i-1]<=j) {
                    maxValue[j]=Math.max(maxValue[j],maxValue[j-a[i-1]]+v[i-1]);
                }
            }
        }
        return maxValue[m];
    }
}